Sweep and Prune

释义 Definition

Sweep and prune：一种常用于碰撞检测（broad phase，粗阶段）的算法/策略。它通过在某个轴上对物体的包围体（常见为 AABB 的端点）进行排序与扫描（sweep），快速找出可能重叠的候选对，并剔除（prune）明显不可能碰撞的组合，从而减少后续精确检测的计算量。（在不同领域也可能有类似“扫描并删减/剪枝”的引申用法。）

发音 Pronunciation (IPA)

/swiːp ænd pruːn/

例句 Examples

We use sweep and prune to find potential collisions.
我们用 sweep and prune 来找出可能发生碰撞的物体组合。

By sorting AABB endpoints each frame, sweep and prune can greatly reduce the number of pairwise checks in a crowded scene.
通过每一帧对 AABB 端点排序，sweep and prune 能在物体密集的场景中大幅减少两两检测的次数。

词源 Etymology

该术语由两个常见动词组合而来：sweep（“扫过、扫描”）描述沿轴线移动并检查重叠区间的过程；prune（“修剪、删减”）表示把不可能相交/碰撞的候选项剔除。作为计算机图形学与物理引擎中的术语，它属于形象化的比喻命名。

相关词 Related Words

• Broadphase
• Collision
• Overlap
• Aabb
• Bounding
• Culling
• Sorting
• Partitioning

文学与作品 Works

• Real-Time Collision Detection（Christer Ericson）——在实时碰撞检测章节中讨论粗阶段方法，常提到 sweep and prune。
• Game Engine Architecture（Jason Gregory）——介绍引擎中的物理/碰撞系统时，常涉及 broad-phase 技术与相关术语。
• Physics for Game Developers（David M. Bourg, Bryan Bywalec）——讨论游戏物理与碰撞检测流程时，会出现包括 sweep and prune 在内的典型方案。